import java.util.*;

public class text {
   //统计一篇英语文章中出现单词的个数；
    //方法：1.建设一个哈希桶，引用Map；
    //.....2.一一进行遍历判断这个哈希表中是否有这个单词；如果没有就进行新添加；
    //......如果有进行在原有的基础上进行相加即可；
    public static Map<String,Integer> countWord(String[] words){
        Map<String,Integer> map=new HashMap<>();
        for(String s:words){
            if(map.get(s)==null){
                map.put(s,1);
            }else{
                int val= map.get(s);
                map.put(s,val+1);
            }
        }
        return map;
    }
    public static void main(String[] args) {
        String[] words = {"hello", "abc", "hello", "def", "this", "this", "this"};
        Map<String, Integer> map = countWord(words);
        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
        for (Map.Entry<String, Integer> entry : entrySet) {
            System.out.print("key: " +   entry.getKey()   + " val: " + entry.getValue());
            System.out.println();
        }

    }
    //找出只出现一次的数字；
    //方法：1.将要遍历的数组元素一一进行放入集合中，
    // 2.在放入得过程中判断是否集合中已经有该元素了，如果有就将该元素取出，如果没有就将该元素放进去；
    //3.在进行一次遍历判断最后剩下的呢个元素就是要找的只出现一次的数字；
    public int singleNumber(int[] nums){
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<nums.length;i++) {
            if(set.contains(nums[i])){
                set.remove(nums[i]);
            }else{
                set.add(nums[i]);
            }
        }
        for(int i=0;i<nums[i];i++){
            if(set.contains(nums[i])){
                return nums[i];
            }
        }
        return -1;
    }
//复制带随机指针的链表；
    //方法：1。先进行遍历一次该链表，拷贝其每个结点的值；
    //.....2.遍历的同时记录其entry的值；方便记录下次找到随机指针要找到的下一个结点；
    //.....3.当遍历完毕后cur在重新指向头节点；进行连接随机指针指向的下一个结点；
public static Node copyRandomList(Node head){
        HashMap<Node,Node> map=new HashMap<>();
        Node cur=head;
        while(cur!=null){
            Node node=new Node(cur.val);
            map.put(cur,node);//key:老结点；//val:新结点；
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
}

//坏键盘打字；
    //方法：1.将键盘坏后实际输入的字母一一遍历放入到集合Set中
    //.....2.接着将想要输入的字母一一遍历与实际输入的字母进行比较，看集合中是否有这些字母，那个没有就说明是坏了的键；
    //注意：可能输入的字母有是正好都是同一个坏了的键，就需要建立一个坏键集合存放这些字母以防多次重复判断；
    public static  void fun(String str1,String str2){
        str1=str1.toUpperCase();
        str2=str2.toUpperCase();
        HashSet<Character> setAct=new HashSet<>();
        for(int i=0;i<str2.length();i++){
            char ch=str2.charAt(i);
            setAct.add(ch);
        }
        HashSet<Character> setBreak=new HashSet<>();
        for(int i=0;i<str1.length();i++){
            char ch=str1.charAt(i);
            if(!setAct.contains(ch)&&!setBreak.contains(ch)){
                setBreak.add(ch);
                System.out.println(ch);
            }
        }

    }
    //宝石与石头；
    //方法：新建一个集合，将所有的宝石放入到这个集合中，然后进行遍历所有的石头，若石头中有宝石就加一，最后获得这些石头中有多少宝石；
    public int numJewelsInStones(String jewels,String stones){
        HashSet<Character> set=new HashSet<>();
        for(int i=0;i<jewels.length();i++){
            char ch=jewels.charAt(i);
            set.add(ch);
        }
        int count=0;
        for(int i=0;i<stones.length();i++){
            char ch1=stones.charAt(i);
            if(set.contains(ch1)){
                count++;
            }
        }
        return count;
    }

//获取前K个高频单词：
    //思路：1,统计每个单词出现的次数；
    //.....因为要找前k个所有一下就想到了前面学到的Top-k问题；
    //....2.建立小根堆；进行判断value值的大小，找value值最大的前k个元素；
    //....如果出现value相同的情况，就需要按照字母顺序表进行判断key的大小，
    //....如果出现value和key值都相同的情况就需要设置小根堆的顺序，需要将这两个特殊的转换成大根堆进行排序后才是正确的；
    //.....由于是进行小根堆的堆排序，所以当将前k个高频单词放入顺序表中；但会出现倒置，这是需要进行倒置
    public List<String> topKFrequent(String[] words,int k){
        HashMap<String ,Integer> map=new HashMap<>();
        //统计每个单词出现的次数；
        for(String word:words){
            if(!map.containsKey(word)){
                map.put(word,1);
            }else{
                int val=map.get(word);
                map.put(word,val+1);
            }
        }
        //2.进行小根堆的构建；
        PriorityQueue<Map.Entry<String,Integer>> minQueue=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //3,遍历Map;
for(Map.Entry<String,Integer> entry:map.entrySet()){
    if(map.size()<k){
        minQueue.offer(entry);
    } else {
        Map.Entry<String,Integer> top=minQueue.peek();
        if(top.getValue().compareTo(entry.getValue())<0){
            minQueue.poll();
            minQueue.offer(entry);
        } else if (top.getValue().compareTo(entry.getValue())==0) {
            if(top.getKey().compareTo(entry.getKey())>0){
                minQueue.poll();
                minQueue.offer(entry);
            }
        }
    }
}

ArrayList<String> arrayList=new ArrayList<>();
for(int i=0;i<k;i++){
    Map.Entry<String,Integer> tmp=minQueue.poll();
    arrayList.add(tmp.getKey());
}
Collections.reverse(arrayList);
return arrayList;
    }


}
